from typing import List

from typing_extensions import Self
import pydantic


EVENT_START = 1
EVENT_END = -1


class TimeLine(pydantic.BaseModel):
    """
    时间线段
    """
    # 开始时间戳
    start: int

    # 结束时间戳
    end: int

    @pydantic.model_validator(mode='after')
    def other_validate(self) -> Self:
        if self.start > self.end:
            raise ValueError('时间段开始时间不能大于结束时间')

        return self


class EventPoint(pydantic.BaseModel):
    """
    事件点
    """
    # 时间戳
    timestamp: int

    # 事件类型
    event: int  # Literal[-1, 1]

    @pydantic.model_validator(mode='after')
    def other_validate(self) -> Self:
        if self.event not in (EVENT_START, EVENT_END):
            raise ValueError('事件点类型只能是-1或1')

        return self


class TimeLineSweeper:
    """
    扫描线算法（整体并发数检查）
    计算请求时间段内的最大并发数

    步骤：
    收集相关"时间线"：筛选所有与 "扫描区间" 重叠的"时间线"。
    生成事件点：将相关"时间线"的开始（+1）和结束（-1）时间作为事件。
    扫描线算法：按时间排序事件，遍历时维护计数器，记录最大值。
    """

    def __init__(self, time_lines: List[TimeLine]):
        self.time_lines = time_lines

    @staticmethod
    def _build_events(time_lines: List[TimeLine], sweep_range: TimeLine) -> List[EventPoint]:
        """
        生成事件点（类型：开始+1，结束-1）

        :param time_lines: 时间段（会议开始和结束时间戳信息）
        :param sweep_range: 扫描区间
        """
        # 筛选重叠的时间段
        overlapping = [m for m in time_lines if m.start < sweep_range.end and m.end > sweep_range.start]

        # 生成事件点（类型：开始+1，结束-1）
        events = []
        for m in overlapping:
            events.append(EventPoint(timestamp=m.start, event=EVENT_START))
            events.append(EventPoint(timestamp=m.end, event=EVENT_END))

        return events

    @staticmethod
    def _sort_events(events: List[EventPoint]):
        """
        首先根据时间排序。
        如果时间相同，我们优先处理结束事件（-1），因为如果两个会议同时开始和结束，我们希望先释放会议室，再开始新的会议。
        """
        events.sort(key=lambda x: (x.timestamp, x.event))
        return events

    def _sweep_max_concurrent(self, events: List[EventPoint]) -> int:
        """
        扫描计算最大并发数
        """
        events = self._sort_events(events)
        max_concurrent = current = 0
        for ev in events:
            current += ev.event
            max_concurrent = max(max_concurrent, current)

        return max_concurrent

    def range_max_concurrent(self, sweep_range: TimeLine, contain_sweep_range: bool = False) -> int:
        """
        扫描给定时间区间内的最大并发数

        :param sweep_range: 扫描区间
        :param contain_sweep_range: True：被扫描的“时间线段”包含扫描区间sweep_range
        """
        events = self._build_events(time_lines=self.time_lines, sweep_range=sweep_range)

        if contain_sweep_range:
            events.append(EventPoint(timestamp=sweep_range.start, event=EVENT_START))
            events.append(EventPoint(timestamp=sweep_range.end, event=EVENT_END))

        return self._sweep_max_concurrent(events=events)
